package it.storm.solution;

/**
 * 1094. 拼车
 * https://leetcode-cn.com/problems/car-pooling/
 */
public class Solutions_1094 {
    public static void main(String[] args) {
//        int[][] trips = {{2, 1, 5}, {3, 3, 7}};
//        int capacity = 4;  // output: false

//        int[][] trips = {{2, 1, 5}, {3, 3, 7}};
//        int capacity = 5;  // output: true

//        int[][] trips = {{2, 1, 5}, {3, 5, 7}};
//        int capacity = 3;  // output: true

        int[][] trips = {{3, 2, 7}, {3, 7, 9}, {8, 3, 9}};
        int capacity = 11;  // output: true

        boolean result = carPooling(trips, capacity);
        System.out.println(result);
    }

    /**
     * 解题思路：
     * 通过绘制一条坐标轴模拟某车站的上车、下车人数，即可得到该解法
     */
    public static boolean carPooling(int[][] trips, int capacity) {
        // 先下后上，那么直接在 trips[n][2] 上进行减，而不用到 trips[n][2] + 1 上进行减
        // counts[3] = 5：表示在车站 3 时，上车 5 人
        // counts[3] = -5：表示在车站 3 时，下车 5 人
        int[] counts = new int[1001];
        for (int[] trip : trips) {
            // 在 trip[1] 站，共有上车人数 trip[0] 人
            counts[trip[1]] += trip[0];
            // 在 trip[2] 站，共有下车人数 trip[0] 人
            counts[trip[2]] -= trip[0];
        }
        // 车上的人数
        int temp = 0;
        for (int cnt : counts) {
            temp += cnt;
            if (temp > capacity) {
                // 超载了，那么无法完成接送所有乘客的任务
                return false;
            }
        }
        return true;
    }
}
